The rise of multimedia computing appliances and digital video transmission has led to an increased need to store and manipulate many-colored and complex digital images. Examples of many-colored and complex digital images include: digital photographic images of the natural world, whether taken with a digital camera or digitized from an analog camera print; computer-generated images of the natural world; and/or computer-generated images which include anti-aliased text or graphics.
Due to the complexity of many-colored digital images, it is often necessary to compress the images in order to save storage space and/or minimize bandwidth when storing or transmitting the digital images. The compression/decompression process typically uses standardized algorithms well known to those of skill in the art. The algorithms for compressing and decompressing the images are known generically as COmpressor/DECompressors or “codecs”.
Codecs are typically grouped into two main types; lossless and lossy. Lossless codecs, like LZ coding and GIF, preserve the image information in its exact form. While providing virtually perfect image replication capabilities, lossless codecs tend to provide less compression opportunities and require more resources, such as storage space and transmission bandwidth, to employ. On the other hand, lossy codecs, such as JPEG and vector quantization, store only an approximate representation of the image. Lossy codecs are typically formulated based on the capabilities and limitations of the human visual system to detect subtle differences in color. In other words, granularity and detail beyond that capable of being detected by the human eye are disregarded and do not survive the compression process. Since, using lossy codecs, digital information is selectively discarded, lossy codecs typically achieve much better compression than lossless codecs while still maintaining acceptable quality.
Once digital information has undergone a lossy compression/decompression, there is little or no point in ever using lossless compression on the information again. This is because the irrelevant data has already been disregarded so that any lossless compression/decompression would, in effect, result in using extra resources to try to save information that has already been lost. In contrast, further lossy compressions/decompressions of digital information that has undergone a lossy compression/decompression already has very little, if any, affect on the resulting image quality.
In light of the discussion above, it is clear that once information has undergone a lossy compression/decompression using a lossy codec, all further compressions/decompressions should probably also be conducted using a lossy codec in order to achieve a high compression ratio and avoid wasting the precious resources associated with lossless compression/decompression. However, in the prior art, there was no mechanism for determining whether a given digital image, or block of digital information, had previously undergone a lossy or lossless compression/decompression and, therefore, there was no mechanism for determining whether the resources required for a lossless compression/decompression should be committed or not. Consequently, in the prior art, it was either deemed safest to commit the considerable resources associated with lossless compression/decompression on all images or to sacrifice image quality across the board. Of course, this resulted in inefficient use of resources and often resulted in unnecessarily degraded images.
As an example, consider a program in the prior art that needed to compress a digital image with an unknown history. One example would be an image-editing program that had imported a ppm file containing raw RGB values. Suppose now that the program wanted to export the image. It may be that the ppm file was generated by decoding a JPEG file, a lossy codec, but the program had no prior-art way of knowing if this was the case. In this instance, lossless compression would be desirable for images of “lossless-origin” that had never been subject to a lossy compression step in order to preserve quality. On the other hand, lossy compression would be preferred for images of “lossy-origin” that had already been subject to a lossy compression step in order to improve the compression ratio and save resources. However, as noted above, in the prior art, there was no mechanism for determining whether a given digital image, or block of digital information, had previously undergone a lossy or lossless compression/decompression and, therefore, there was no mechanism for determining whether the resources required for a lossless compression/decompression should be committed or not. Consequently, the choice was presented of either risking a poor compression ratio and inefficient use of resources or potentially losing image quality.
Another example of an situation where there is a need to compress an image with no knowledge of its source is in remote computing applications. There are several different remote-computing applications where screen information is generated on one computer, the “host” computer, and transmitted for display on another computer, the “display” computer. In some systems, the display computer is a multipurpose computer, an X-terminal, a thin-client, or a Personal Digital Assistant (PDA). X-terminals, thin-clients, and Personal Digital Assistants (PDAs) are limited-purpose computers, some having no hard drive and some designed only for remote computing applications. In these instances, the host and display computers can communicate via any sort of network connection, including wireless. Consequently, in remote computing applications, it is frequently desirable to reduce the network bandwidth used because doing so provides shorter transmission times between the host and display computers, leading to a faster-updating remote display device and reduced load on the network, leading to improved network performance. In addition, reducing the network bandwidth used by remote computing applications provides the capability to use more devices on a single network. For typical computing, including web browsing, the host/display network bandwidth will in many cases be dominated by the transmission of digital images with a large number of colors. Thus, some remote display applications use lossless and/or lossy digital image codecs to compress such images for lower-bandwidth transmission. Once again, it would be extremely helpful to know if a lossless or lossy codec were previously used on a given image. Web browsing is a common source of many-colored images. Many web pages contain digital photographs that have been compressed using lossless codecs like GIF or PNG or lossy codecs such as JPEG. In the prior art, the remote display application's host computer typically knew the RGB values of the decoded image, but did not know how the image was originally encoded. Again, it would be efficient to use a lossless codec to encode lossless-origin images and a lossy codec to encode lossy-origin images. This information would be particularly valuable at bandwidths where the lossy codec is noticeably faster to paint, due to its higher compression ratio, but where the lossy codec paint speed is still acceptable. Unfortunately, as discussed above, in the prior art there was no mechanism for determining whether a given digital image, or block of digital information, had previously undergone a lossy or lossless compression/decompression and, therefore, there was no mechanism for determining whether the resources required for a lossless were necessitated.
What is needed is a method of determining whether an image is of lossy-origin of lossless origin prior to a subsequent compression/decompression.